package interview.demo1;

import java.lang.reflect.Array;

/**
 * 冒泡算法：
 *  原理：实现了双层循环，内层循环将相邻两个数进行两两比较，
 *  将最大的一个数以冒泡（两两交换）的形式传送最队尾，
 *  一次只能将一个最大值传送到队尾；而外层循环实现了依次将当前最大值传送，
 *  最终实现排序；
 * 5位数的数组需要4躺排序的，每躺排序之后次数减1
 * (因为前一趟已经把前一趟数的最大值确定下来了)！
 *
 * @author
 * @create 2018-10-12 10:50
 **/
public class BubbleSore {

    public static void main(String[] args) {


        int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2};

        int[] array = {10, 9, 1, 2, 3};
        int[] array1 = {10, 9, 1, 2, 3};

        System.out.print("排序之前的数组：");
        for (int temp : array) {
            System.out.print(temp);
        }
        System.out.println();
        array = BubbleSore(array);
        System.out.print("原生的排序后的数组：");
        for (int temp : array) {
            System.out.print(temp);
        }
        System.out.println();
        System.out.println("--------------------------------");
        //优化后的排序
        System.out.print("排序之前的数组：");
        for (int temp : array1) {
            System.out.print(temp);
        }
        System.out.println();
        array1 = BubbleSore1(array1);
        System.out.print("优化后的排序后的数组：");
        for (int temp : array1) {
            System.out.print(temp);
        }

        System.out.println();
        System.out.println("------------------------------");
        //优化后的排序
        System.out.print("递归排序之前的数组：");
        for (int temp : arrays) {
            System.out.print(temp+" ");
        }
        System.out.println();
        bubbleSore3(arrays, 0, arrays.length-1);
        System.out.print("递归后的数组：");
        for (int temp : arrays) {
            System.out.print(temp+" ");
        }

    }

    /**
     * 原生的冒泡排序
     *
     * @param array
     * @return
     */
    public static int[] BubbleSore(int[] array) {

        //记录比较的趟数
        int number = 0;
        //外面循环次数:5个数字要经过4次循环
        for (int i = 0; i < array.length - 1; i++) {
            //5个数字则要进行4次比较，并且每趟下来，比较次数减1，因为最大的数已经在最后一位，不需要比较
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
            number++;
        }
        System.out.println("比较的趟数" + number);
        return array;
    }


    /**
     * 优化冒泡排序算法：
     * 如果在某躺排序中没有发生交换位置，那么我们可以认为该数组已经排好序了。
     * 因为我们每趟排序的目的就是将当前趟最大的数置换到对应的位置上，
     * 没有发生置换说明就已经排好序了。所以我们可以设置一个标志，当这个标志位没有
     * 发生改变的时候，我们则跳出整个循环不再进行排序了
     *
     * @param array
     * @return
     */
    public static int[] BubbleSore1(int[] array) {
        int temp = 0;
        int change;
        //记录排序了几趟
        int number = 0;

        for (int i = 0; i < array.length - 1; i++) {
            change = 0;
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    change = 1;
                }
            }
            //如果该趟没有发生位置的调换，则直接跳出循环
            if (change == 0) {
                break;
            }
            //每一趟排序比较则+1
            number++;
        }
        System.out.println("该排序比较的趟数：" + number);
        return array;

    }

    /**
     * 递归的冒泡排序
     */
    public static void bubbleSore3(int[] array, int left, int right) {
        //递归出口
        if (left == right) {
            return;
        } else {
            for (int i = left; i < right; i++) {
                if (array[i] > array[i + 1]) {
                    int temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                }

                //第一趟后，则最后一个数作为1，前面部分作为一个整体
                bubbleSore3(array, left, right - 1);
            }
        }

    }
}
